package main

func main() {

	println(maxSubArray0([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}))
	println(maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}))
}

func maxSubArray0(nums []int) int {
	// 1-- 动态规划版本；；动态规划核心思想：若前一个元素大于0，则将其加到当前元素上
	if len(nums) == 1 {
		return nums[0]
	}

	max := nums[0]

	for i := 1; i < len(nums); i++ {
		// 1. 若之前一个元素> 0,则将其加到当前元素上
		if nums[i-1] > 0 {
			nums[i] = nums[i] + nums[i-1]
		}

		if nums[i] > max {
			max = nums[i]
		}
	}

	return max

}
func maxSubArray(nums []int) int {

	// 2-- 贪心算法版本 : 若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列。若当前指针所指元素之前的和大于等于0，则将之前和 + 当前值。

	if len(nums) == 1 {
		return nums[0]
	}

	// 最大值
	max := nums[0]
	// 之前和
	sum := nums[0]

	for i := 1; i < len(nums); i++ {

		if sum < 0 {
			// 1. 之前和 小于0 ，则丢弃之前和。当前和 = 当前值
			sum = nums[i]
		} else {

			// 2. 之前和 >= 0, 则当前和 = 之前和 + 当前值
			sum = sum + nums[i]
		}

		if sum > max {
			max = sum
		}

	}

	return max

}
